import java.util.*;
import java.util.concurrent.PriorityBlockingQueue;

//堆
/*
1，一棵完全二叉树，顺序存储（数组）层序遍历非完全二叉树则不用数组存储，因为空间利用率低
2，分为小根堆（每棵子树都是小根堆）和大根堆
3，孩子下标2i+1和2i+2，父亲节点的下标i-1/2
 */
class Heap{
    public  int [] elem;
    public int useSize;
    public Heap(){
        elem=new int[10];
    }
    public void inti(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            useSize++;
        }
    }
    //大根堆
    /**
     * chile:储存的是左,右孩子的最大值的下标
     */
    private void swap(int i,int j){
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;
    }

    /**
     * 向下调整
     * 时间复杂度O(log2(n))
     */
    public void siftDown(int parent,int end){
        int child=parent*2+1;
        while (child<end){
            if (child+1<end && elem[child]<elem[child+1]){
                child++;
            }
            if (elem[child]>elem[parent]){
                swap(child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

    /**
     * 时间复杂度：O（n）
     */
    public void createHeap(){
        for (int parent =(useSize-1-1)/2 ; parent >=0; parent--) {
            siftDown(parent,useSize);
        }
    }

    private boolean isFull(){
        return  elem.length==useSize;
    }
    /**
     * 时间复杂度：O（n）
     */
     public void offer(int val){
        if (isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[useSize]=val;
        useSize++;
        siftUp(useSize-1);
     }
     private void siftUp(int child){
        int parent=(child-1)/2;
        while (parent>=0){
            if (elem[child]>elem[parent]){
                swap(child,parent);
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
     }
     //删掉一个元素(交换，向上调整)
    /**
     * 时间复杂度：O（n）
     */
    public int poll(){
        if (isEmpty()){
            return -1;
        }
        int old=elem[0];
        swap(0,useSize-1);
        useSize--;
        siftDown(0,useSize);
        return old;
    }
    private boolean isEmpty(){
        return useSize==0;
    }
    /**
     ** 堆排序：O（n*log2(n)）
     * 时间复杂度：
     * 从小到大
     * 先搞成大根堆
     *下标0和最后一个交换
     */
    public void heapSort(){
        int endIndex=useSize-1;
        while (endIndex>0){
            swap(0,endIndex);
            siftDown(0,endIndex);
            endIndex--;
        }
    }


}

class Student{

}
class InCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }//大根堆

    /*@Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }//小根堆*/

}

public class Test {


    /**
     * 找前K个最小的数字：
     *时间复杂度：O（（n+k）log2（n））
     */
    public int[]smallestK(int [] arr,int k){
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            queue.offer(arr[i]);
        }
        int[] tmp=new int[k];
        for (int i = 0; i <k; i++) {
            tmp[i]=queue.poll();
        }
        return tmp;
    }
    //优化：
    /*
    先建立大小为k的大根堆，对顶元素大于i下标的值就出去，
     */
    /**
     *时间复杂度：O（nlog2（n））
     * 也可以求第k大或者第k小的数字
     */
    public int[]smallestK2(int [] arr,int k){
        int[] tmp=new int[k];
        if (k==0){
            return tmp;
        }
        PriorityQueue<Integer> maxHead=new PriorityQueue<>(new InCmp());
        //1，先把看个元素放到元素中
        for (int i = 0; i <k; i++) {
            maxHead.offer(arr[i]);
        }
        //2，遍历剩下的元素
        for (int i = k; i < arr.length; i++) {
            int val=maxHead.peek();
            if (val>arr[i]){
                maxHead.poll();
                maxHead.offer(arr[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            tmp[i]=maxHead.poll();
        }
        return tmp;
    }



    public static void main3(String[] args) {
        PriorityQueue<Integer>priorityQueue=new PriorityQueue<>(new InCmp());

    }
    public static void main(String[] args) {
        //默认是一个小根堆,容量默认为11
        PriorityQueue<Integer>priorityQueue=new PriorityQueue<>();
        priorityQueue.offer(12);
        priorityQueue.offer(5);
        priorityQueue.offer(57);
        System.out.println(priorityQueue.poll());
        /*PriorityQueue<Student>priorityQueue2=new PriorityQueue<>();
        //priorityQueue2.offer(null);
        priorityQueue2.offer(new Student());*/

        //多线路安全
        //PriorityBlockingQueue
        ArrayList<Integer>list=new ArrayList<>();
        list.add(21);
        list.add(27);
        list.add(5);
        PriorityQueue<Integer>priorityQueue3=new PriorityQueue<>(list);
        System.out.println(priorityQueue3.poll());//5

    }
    public static void main2(String[] args) {
        int[] array={27,15,19,18,28,34,65,49,25,37};
        Heap heap=new Heap();
        heap.inti(array);
    }

}
